import java.util.ArrayList;
/*
 * This class represents Tablero state at first or then of a movement
 */
public class Tablero
{
    private Tablero padre;                                          //to get father node
    private ArrayList<Integer> fichas= new ArrayList<Integer>();    //contains Integer values to represent existing positions see readme.txt
    private ArrayList<Tablero> ramas=new ArrayList<Tablero>();      //contains node branches 
    private ArrayList<Integer> vacios=new ArrayList<Integer>();     //contains illegal positions values 
    private ArrayList<String> camino=new ArrayList<String>();       //store valid movements
    
    public Tablero(ArrayList<Integer> sFichas, ArrayList<Integer> sVacios, ArrayList<String> sCamino, Tablero sPadre)
    {
        padre=sPadre;
        vacios=sVacios;
        camino=sCamino;
        for(int i=0;i<sFichas.size();i++)
        {
            fichas.add(sFichas.get(i));
        }
    }
    
    public Tablero()
    {
        iniciar();
    }
    
    public void crearVacios()
    {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<=10;j++)
            {
                int pos=10*i+j;
                if(10*i+j>10*i+7||pos==11||pos==12||pos==16||pos==17||pos==21||pos==22||pos==26||pos==27||pos==61||pos==62||pos==66||pos==67||pos==71||pos==72||pos==76||pos==77||pos<=12||pos>=77)
                {
                    vacios.add(10*i+j);
                }
            }
        }
    }
    
     public boolean esVacio(int pos)
    {
        return vacios.contains(pos);
    }
    
    public void iniciar()
    {
        crearVacios();
        fichas.add(0);
        for(int j=1;j<=7;j++)
        {
            for(int i=1;i<=7;i++)
            {
                int pos=i+10*j;
                if(!esVacio(pos)&&pos!=44)
                {
                    fichas.add(pos);
                }
            }
        }
    }
    
    public int buscar(int n)
    {
        for(int j=0;j<fichas.size();j++)
        {
            if(fichas.get(j)==n)
            {
                return j;
            }
        }
        return 0;
    }
    
    public boolean existe(int pos)
    {
        return fichas.contains(pos);
    }
    
    public void arriba(int pos)
    {
       if( existe(pos-10) && (!existe(pos-20)) && (!esVacio(pos-20)) )
       {
           Tablero p;
           ramas.add(p=new Tablero(fichas,vacios,camino,this));
           ramas.get(ramas.indexOf(p)).agregar(pos-20); 
           ramas.get(ramas.indexOf(p)).quitar(pos-10);
           ramas.get(ramas.indexOf(p)).quitar(pos);
           camino.add(pos+"-"+(pos-20));
           ramas.get(ramas.indexOf(p)).resolver(); 
       }
    }
    
     public void derecha(int pos)
    {
       if( existe(pos+1) && (!existe(pos+2)) && (!esVacio(pos+2)) )
       {
           Tablero p;
           ramas.add(p=new Tablero(fichas,vacios,camino,this));    
           ramas.get(ramas.indexOf(p)).agregar(pos+2);   
           ramas.get(ramas.indexOf(p)).quitar(pos+1);   
           ramas.get(ramas.indexOf(p)).quitar(pos);
           camino.add(pos+"-"+(pos+2));
           ramas.get(ramas.indexOf(p)).resolver();
       }
    }
    
     public void abajo(int pos)
    {
       if( existe(pos+10) && (!existe(pos+20)) && (!esVacio(pos+20)) )
       {
           Tablero p;
           ramas.add(p=new Tablero(fichas,vacios,camino,this));     
           ramas.get(ramas.indexOf(p)).agregar(pos+20);  
           ramas.get(ramas.indexOf(p)).quitar(pos+10);   
           ramas.get(ramas.indexOf(p)).quitar(pos);
           camino.add(pos+"-"+(pos+20));
           ramas.get(ramas.indexOf(p)).resolver();
       }
    }
    
     public void izquierda(int pos)
    {
       if( existe(pos-1) && (!existe(pos-2)) && (!esVacio(pos-2)) )
       {
           Tablero p;
           ramas.add(p=new Tablero(fichas,vacios,camino,this));     
           ramas.get(ramas.indexOf(p)).agregar(pos-2);  
           ramas.get(ramas.indexOf(p)).quitar(pos-1);
           ramas.get(ramas.indexOf(p)).quitar(pos);
           camino.add(pos+"-"+(pos-2));
           ramas.get(ramas.indexOf(p)).resolver();
       }
    }
    
    public void quitar(int pos)
    {
        fichas.remove(buscar(pos));
    }
    
    public void agregar(int pos)
    {
        fichas.add(pos);
    }
    
    public void podar(int i)
    {
        ramas.remove(i);
    }
    
    public void podar(Tablero t)
    {
        ramas.remove(ramas.indexOf(t));
    }
    
    public int nRamas()
    {
        return ramas.size();
    }
    
    public Tablero getRama(int i)
    {
      return ramas.get(i); 
    }
    
    public Tablero getRama(Tablero t)
    {
        return ramas.get(ramas.indexOf(t));
    }
    
    public void resolver()
    {
        boolean flag=false;
        for(int j=1;j<fichas.size();j++)
        {
            int pos=fichas.get(j);
            arriba(pos);
            derecha(pos);
            abajo(pos);
            izquierda(pos);
        }
        
        if(ramas.size()==0)
        {    
            if(fichas.size()==2)     
            {   
                
                for(int i=0;i<camino.size();i++)       
                {         
                    System.out.print(camino.get(i)+",");       
                }
                System.out.println();
            }    
            camino.remove(camino.size()-1);
            padre.podar(padre.getRama(this));
        }
    }
}